package com.zlsy.learning.leetcode.arraycorrelation.array1395;

/**
 * @author zhouliang
 * @date 2020/6/11 21:25
 */
public class NumTeams {
    /**
     * 遍历中间的士兵，统计 左边/右边 比他 小/大 的士兵人数。
     * <p>
     * 每名士兵在中间的情况下可以组队的数量为：
     * 左边比他小的人数 × 右边比他大的人数 + 左边比他大的人数 × 右边比他小的人数
     * <p>
     * 公式为：left[0] * right[1] + left[1] * right[0]
     * ​
     * (left[0]∗right[1]+left[1]∗right[0])
     */
    private static int numTeams(int[] rating) {
        int n = rating.length;
        int result = 0;
        for (int i = 0; i < n; ++i) {
            int[] left = count(rating, 0,
                    i, rating[i]);
            int[] right = count(rating, i, n, rating[i]);
            result += left[0] * right[1] + left[1] * right[0];
        }
        return result;
    }

    private static int[] count(int[] rating, int from, int to, int key) {
        int[] results = new int[2];
        for (int i = from; i < to; ++i) {
            if (rating[i] < key) {
                ++results[0];
            } else if (rating[i] > key) {
                ++results[1];
            }
        }
        return results;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 5, 3, 4, 1};
        for (int i = 0; i < nums.length; ++i) {
            System.err.println(i);
            int num = nums[i];
            System.out.println(num);
        }
    }
}
